package cn.edu.njust.alg.leetcode;

/**
 * 创建时间：2015年6月15日 上午11:47:37 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Leetcode_0_t.java 类说明：
 */

/**
 * Definition for singly-linked list. public class ListNode { int val; ListNode
 * next; ListNode(int x) { val = x; next = null; } }
 */
public class Leetcode_160_Intersection_of_Two_Linked_Lists {

	public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		int len1 = 0;
		int len2 = 0;
		int diff = 0;
		ListNode p, q;
		p = headA;
		while (p != null) {
			p = p.next;
			len1++;
		}
		// System.out.println("len1:" + len1);
		p = headB;
		while (p != null) {
			p = p.next;
			len2++;
		}
		p = headA;
		q = headB;
		if (len1 > len2) {
			diff = len1 - len2;
			while (diff != 0) {
				p = p.next;
				diff--;
			}
		} else {
			diff = len2 - len1;
			while (diff != 0) {
				q = q.next;
				diff--;
			}
		}
		while (p != null && q != null) {
			if (p == q) {
				return p;
			} else {
				p = p.next;
				q = q.next;
			}
		}

		return null;
	}

	public static void main(String[] args) {
		ListNode A1 = new ListNode(1);
		ListNode A2 = new ListNode(2);
		ListNode A3 = new ListNode(45);
		A1.next = A2;
		A2.next=A3;

		ListNode B1 = new ListNode(1);
		ListNode B2 = new ListNode(1);
		B1.next = B2;
		ListNode C1 = new ListNode(3);
		A3.next = C1;
		B2.next = C1;
		System.out.println(getIntersectionNode(A1, B1).val);
	}

}
